package com.gaofeng.algo.java;

import java.util.Arrays;
import java.util.List;

public class DynamicProgramJava {


    public int climbStairs(int n) {
        if (n < 3) {
            return n;
        }
        int first = 1;
        int second = 2;
        int current = 0;
        for (int i = 3; i <= n; i++) {
            current = first + second;
            first = second;
            second = current;
        }
        return current;
    }

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int size = nums.length;
        int[] dp = new int[size + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= size; i++) {
            int current = dp[i - 2] + nums[i - 1];
            dp[i] = Math.max(current, dp[i - 1]);
        }

        return dp[size];
    }

    public int rob1(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int size = nums.length;
        if (size == 1) {
            return nums[0];
        }
        int first = 0;
        int second = 0;
        int current = 0;
        for (int i = 0; i < size; i++) {
            current = Math.max(second, first + nums[i]);
            first = second;
            second = current;
        }
        return current;
    }

    public int numberOfArithmeticSlices(int[] A) {
        if (A.length < 3) {
            return 0;
        }
        int[] dp = new int[A.length];
        int sum = 0;
        for (int i = 2; i < A.length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                sum += dp[i];
            }
        }
        return sum;
    }

    public int minPathSum(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 这里可以对空间进行压缩的
     * 用一维的空间来表示dp
     *
     * @param grid
     * @return
     */
    public int minPathSum2(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[j] = grid[i][j];
                } else if (i == 0) {
                    dp[j] = dp[j - 1] + grid[i][j];
                } else if (j == 0) {
                    dp[j] = dp[j] + grid[i][j];
                } else {
                    dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
                }
            }
        }
        return dp[n - 1];
    }


    public int[][] updateMatrix(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[][]{};
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    if (i > 0) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
                    }

                    if (j > 0) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                    }
                }
            }
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    if (i < m - 1) {
                        dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
                    }
                    if (j < n - 1) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
                    }
                }
            }
        }
        return dp;
    }

    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int maxSlide = 0;
        int[][] dp = new int[m][n];
        //遍历搜索
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    //边界条件
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        //记录上次的结果,并更新当前的结果
                        //状态转移方程
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                    }
                    maxSlide = Math.max(maxSlide, dp[i][j]);
                }
            }
        }
        return maxSlide * maxSlide;
    }

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

    /**
     * 已知字母 A-Z 可以表示成数字 1-26。给定一个数字串，求有多少种不同的字符串等价于这个
     * 数字串。
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        int size = s.length();
        if (size == 0) {
            return 0;
        }
        //定义一个dp方程,每一项表示的是以
        //第i个字母结尾,所能代表的个数
        int[] dp = new int[size];
        char[] chars = s.toCharArray();
        //如果第一个字母是0,就没有匹配的
        if (chars[0] == '0') {
            return 0;
        }
        //定义边界是1,第一个字母结尾的个数只能是1
        dp[0] = 1;
        for (int i = 1; i < size; i++) {
            //然后当前字母不是0,那么先将其赋值为上一个字母结尾的个数
            if (chars[i] != '0') {
                //比如 221 有三种 那么2212 以2结尾的个数,将2单独分开必然与以1结尾的个数一样.
                dp[i] = dp[i - 1];
            }
            //然后更新,如果连续的两个数组成的数字在10-26之间
            //比如2212 12满足条件,此时以12结尾的个数 必然与dp[i-2]相等
            //那么dp[i] = dp[i]+dp[i-2]
            int number = 10 * (chars[i - 1] - '0') + (chars[i] - '0');
            if (number >= 10 && number <= 26) {
                if (i == 1) {
                    //边界条件加1即可
                    //比如12 以2结尾的就是12 ,因为上面判断一次,将2分开时dp的值是1,然后在自增结果就是2
                    dp[i]++;
                } else {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[size - 1];
    }

    /**
     * 对于分割类型的动态规划,dp方程的值不取决与相邻的值,而是取决于分割条件
     * 比如这道题.规定dp[0]为true.
     * apple dp[5] = dp[5] || dp[5-5]=dp[0]=true
     * 分割条件是word == 从字符串中截取的单词相等
     * 状态转移方程式dp[i] = dp[i] || dp[i-len] len是单词的长度
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int len = word.length();
                if (i >= len && s.substring(i - len, i).equals(word)) {
                    dp[i] = dp[i] || dp[i - len];
                }
            }
        }
        return dp[n];
    }


    public static void main(String[] args) {
        DynamicProgramJava demo = new DynamicProgramJava();
        for (int i = 1; i <= 17; i++) {
            System.out.println("dp[" + i + "]:" + demo.numSquares(i));
        }
    }
}
